#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define ALPHA_SIZE  (26)

typedef struct _st_hash {
    int alpha[ALPHA_SIZE];
} hash;

int cmp_hash(hash des, hash res)
{
    int i = 0;
    for(; i < ALPHA_SIZE; i++) {
        if(des.alpha[i] < res.alpha[i]) {
            return 0;
        }
    }
    return 1;
}

hash get_from_str(const char *des)
{
    char *p = (char *)des;
    hash ret = {0};
    while(*p) {
        ++ret.alpha[*p - 'a'];
        ++p;
    }
    return ret;
}

void update(hash *des, hash res)
{
    int i = 0;
    for(; i < ALPHA_SIZE; i++) {
        if(des->alpha[i] < res.alpha[i]) {
            des->alpha[i] = res.alpha[i];
        }
    }
}

hash get_from_strs(char **strs, int size)
{
    int i = 0;
    hash ret = {0};
    for(; i < size; i++) {
        hash tmp = get_from_str(strs[i]);
        update(&ret, tmp);
    }
    return ret;
}

char** wordSubsets(char** A, int ASize, char** B, int BSize, int* returnSize) {
    int i = 0;
    int j = 0;
    *returnSize = 0;
    char **ret = NULL;
    hash b_hash = get_from_strs(B, BSize);
    for(i = 0; i < ASize; i++) {
        hash a_hash = get_from_str(A[i]);
        if(cmp_hash(a_hash, b_hash)) {
            ++*returnSize;
            ret = realloc(ret, *returnSize * sizeof(char *));
            ret[*returnSize - 1] = strdup(A[i]);
        }
    }
    return ret;
}